//
//  main.c
//  Questions
//
//  Created by wangrui.
//  Copyright (c) 2014年 wangrui. All rights reserved.
//

/*
 *图(无向)的最小生成树 kruskal算法
 *
 *2014-10-08 09:58:36
 *测试数据:
	9 6
	2 4 11
	3 5 13
	4 6 3
	5 6 4
	2 3 6
	4 5 7
	1 2 1
	3 4 9
	1 3 2
 */

#include <stdio.h>
#include <stdlib.h>
#include "cutils.h"

#ifdef DEBUG
#undef DEBUG
#define DEBUG 0
#endif

typedef struct {
	int u;
	int v;
	int w;
} Edge;

void qickSortEdge(Edge *edges, int begin, int end)
{
	if (begin >= end) {
		return;
	}
	
	int i=begin,j=end;
	int basicW = edges[begin].w;
	
	while (i!=j) {
		
		while (edges[j].w >= basicW && j>i) {
			j--;
		}
		
		while (edges[i].w <= basicW && i<j) {
			i++;
		}
		
		Edge temp = edges[i];
		edges[i] = edges[j];
		edges[j] = temp;
	}
	
	//交换第一个和中间位置的，此时i一定等于j
	Edge temp = edges[begin];
	edges[begin] = edges[i];
	edges[i] = temp;
	
	qickSortEdge(edges,begin,i-1);
	qickSortEdge(edges,i+1,end);
}

//并查集需找首领的函数
int getf(int f[],int idx)
{
	if (f[idx] == idx) {
		return idx;
	}
	
	f[idx] = getf(f,f[idx]);//注意理解这行代码:找父节点的父节点并递归更新下来
	
	return f[idx];
}

//判断两个点是否连通,即有同一个父节点或同一个集合中
//返回1代表未连通
int merge(int f[], int idx, int idx2)
{
	int t1 = getf(f, idx);
	int t2 = getf(f, idx2);
	
	if (t1 != t2) {
		f[t2] = t1; //按左归顺，即右边的值设为左边的father
		return 1;
	}
	
	return 0;
}

int main(int argc, const char * argv[])
{
	int m,n;
	scanf("%d %d",&m,&n);
	
	Edge edges[m+1];
	
	for (int i=1; i<=m; i++) {
		scanf("%d %d %d",&edges[i].u,&edges[i].v,&edges[i].w);
	}
	
	//按权重排序边
	qickSortEdge(edges, 1, m);

#if DEBUG
	for (int i=1; i<=m; i++) {
		printf("%d %d %d\n",edges[i].u,edges[i].v,edges[i].w);
	}
#endif
	
	//并查集使用的变量
	int f[n+1],sum=0,count=0;
	
	for (int i=0; i<n+1; i++) {
		f[i] = i;
	}
	
	for (int i=1; i<=m; i++) {
		
		int success = merge(f,edges[i].u,edges[i].v); //边对应的两点是不是在同一个集合,能不能连通
		
		if (success) {
			count++;
			sum += edges[i].w;
			printf("%d-%d:%d\n",edges[i].u,edges[i].v,edges[i].w);
		}
		
		if (count == n-1) { //如果已经有n-1条边连通，则连通结束, for循环结束后可增加一个判断,判断是否能连通
			break;
		}
	}
	
	//打印权
	printf("min weight:%d\n",sum);
	
	return 0;
}


